// 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

// 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

// 求所能获得硬币的最大数量。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/burst-balloons
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include<bits/stdc++.h>
using namespace std;
// 看了题解，动态规划
// 执行用时：
// 624 ms
// , 在所有 C++ 提交中击败了
// 63.78%
// 的用户
// 内存消耗：
// 9.9 MB
// , 在所有 C++ 提交中击败了
// 46.96%
// 的用户

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        // 增加最左最右1,1：+2
        // 默认为0，dp[i][j]代表i-j间最大的积分，j-i小于3则为0
        vector<vector<int>> dp(nums.size()+2,vector<int>(nums.size()+2,0));
        // 输入数组
        vector<int> num(nums.size()+2,1);
        for(int i=1;i<=nums.size();i++){
            num[i]=nums[i-1];
        }

        // 自底向上，i与j差值必须大于3
        // k在i、j间
        for(int i=dp.size()-2;i>=0;i--){
            for(int j=i+2;j<dp.size();j++){
                for(int k=i+1;k<j;k++){
                    dp[i][j] = max(dp[i][j],dp[i][k]+dp[k][j]+num[i]*num[k]*num[j]);
                }
            }
        }
        return dp[0][nums.size()+1];
    }
};